package com.mc.sort;

import com.mc.general.Tools;

public class QuickSort {
	public static <T extends Comparable<T>> void sort(T[] array){
		sort(array,0,array.length-1);
	}
	private static <T extends Comparable<T>> void sort(T[] array, int low, int high){
		if(high<=low) return;
		int index = partition(array, low, high);
		sort(array,0,index-1);
		sort(array,index+1,high);
	}
	private static <T extends Comparable<T>> int partition(T[] array, int low, int high){
		T target = array[low];
		int i = low;
		int j = high+1;
		while(true){
			while(Tools.compare(array[++i], target)==-1)
				if(i==high)break;
			while(Tools.compare(array[--j], target)==1)
				if(j==low)break;
			if(i>=j)break;//只有边缘处i和j才可能相等
			Tools.exchange(i, j, array);
		}
		Tools.exchange(low, j, array);
		return j;
	}
	public static void sortInt(int[] a,int low ,int high){
		if(low>=high)
			return;
		int index = partition(a,low,high);
		sortInt(a, low, index-1);
		sortInt(a,index+1,high);
		
	}
	public static int partition(int[] a,int low, int high){
		int i=low+1;
		int j=high;
		while(true){
			while(a[i]<a[low]){
				if(i==high)break;
				i++;
			}
			while(a[j]>a[low]){
				if(j==low)break;
				j--;
			}
			if(i>=j)break;	
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		int temp = a[j];
		a[j] = a[low];
		a[low] = temp;
		return j;
	}
	public static void main(String[] args) {
		int[] a = {3,5,12,3,6,7};
		QuickSort.sortInt(a, 0, a.length-1);
		for(int i:a){
			System.out.println(i);
		}
	}
}
